#ifndef _HISTOPYRAMID_H_
#define _HISTOPYRAMID_H_

#include "../cuCommon/cuTypes.h"
#include "../cuCommon/cuBuffer.h"
#include "../rtCommon/Execution.h"

template <class C>
class THistoPyramid
{
protected:
	//////////////////////////////////////////////////////////////////////////
	/// m_nBin holds the total number of bins
	//////////////////////////////////////////////////////////////////////////
	uint32   m_nBin;
	//////////////////////////////////////////////////////////////////////////
	/// m_nBinExp holds the exp value for histogram
	//////////////////////////////////////////////////////////////////////////
	uint32   m_nBinExp;

	//////////////////////////////////////////////////////////////////////////
	/// Null function sets all numerical values to zero and pointers to NULL
	//////////////////////////////////////////////////////////////////////////
	void     Null() 
	{
		m_nBin = 1;
		m_nBinExp = 0;
	}

public:

	//////////////////////////////////////////////////////////////////////////
	/// Ctor / Dtor
	//////////////////////////////////////////////////////////////////////////
	THistoPyramid()  { Null(); }
	~THistoPyramid() { Release(); }

	//////////////////////////////////////////////////////////////////////////
	/// histogram stores nBin counters for n Bins
	//////////////////////////////////////////////////////////////////////////
	TBuffer<C> histogram;

	//////////////////////////////////////////////////////////////////////////
	/// pyramid can only be used (properly) when nBin is a power of two
	/// pyramid holds 2^(nBinExp+1) - 1 values for a pyramid sum
	/// 
	//////////////////////////////////////////////////////////////////////////
	TBuffer<C> pyramid;

	//////////////////////////////////////////////////////////////////////////
	/// scan can hold nBin+1 counters 
	/// where first counter is usually 0 and last counter is EQ to number of
	/// processed elements
	//////////////////////////////////////////////////////////////////////////
	TBuffer<C> scan;

	uint32   nBin()
	{
		return m_nBin;
	}

	void     CreateBin(uint32 nBinExp, 
		                 uint8  cFlags = BUFFER_H,
									   bool   bDouble = false)
	{
		m_nBinExp = nBinExp;

		m_nBin = 1 << m_nBinExp;

		uint32 nBinPyramid = (1 << (m_nBinExp+1)) - 1; // 2^n - 1

		histogram.Create(m_nBin,      cFlags, bDouble);
		scan.Create     (m_nBin+1,    cFlags, bDouble);
		pyramid.Create  (nBinPyramid, cFlags, bDouble);
	}

	void     Create(uint32 nPrimitive, 
									uint8  cFlags = BUFFER_H,
									bool   bDouble = false)
	{
		uint32 iMask = 0x80000000;
		uint32 iBit = 0;

		while ((nPrimitive & (iMask >> 1)) == 0)
		{
			iMask = iMask >> 1;
			iBit++;
		}

		m_nBin = iMask;
		m_nBinExp = 32 - iBit;

		uint32 nBinPyramid = (1 << (m_nBinExp+1)) - 1; // 2^n - 1

		uint32 nBins = ((uint32)((nPrimitive + m_nBin - 1) / m_nBin)) * m_nBin;

		histogram.Create(nBins,       cFlags, bDouble);
		scan.Create     (m_nBin + 1,  cFlags, bDouble);
		pyramid.Create  (nBinPyramid, cFlags, bDouble);
	}

	void     Release()
	{
		histogram.Release( BUFFER_H_AND_D );
		pyramid.Release  ( BUFFER_H_AND_D );
		scan.Release     ( BUFFER_H_AND_D );
	}

	template <class T>
	void     Histogram(TBuffer<T> * pBuffer, 
										 float2     * pIntervalR,
										 float2     * pIntervalW,
		                 uint8        exeFlags,
										 uint8        bufFlags)
	{
		if (exeFlags == EXEC_H)
		{
			bool bR = bufFlags & BUFFER_R;
			bool bW = bufFlags & BUFFER_W;

			T * rPtr = pBuffer->hPtrR();
			T * wPtr = pBuffer->hPtrW();

			C * rHtm = histogram.hPtrR();
			C * wHtm = histogram.hPtrW();

			histogram.Memset(NULL, 0, 0, bufFlags, false);

			float2 intervalR, intervalW;

			float inv_r = 0, inv_w = 0;

			if (bW)
			{
				intervalR = *pIntervalR;
				intervalR.y += EPSILON;
				intervalR.x -= EPSILON;

				inv_r = 1.0f / (intervalR.y - intervalR.x);
			}

			if (bR)
			{
				intervalW = *pIntervalW;
				intervalW.y += EPSILON;
				intervalW.x -= EPSILON;

				inv_w = 1.0f / (intervalW.y - intervalW.x);
			}		

			int32 iBinR = 0;
			int32 iBinW = 0;

			for (uint32 iT = 0; iT < pBuffer->size(); iT++)
			{
				if (bW)
				{
					iBinW = (rPtr[iT].x - intervalW.x) * inv_w * m_nBin;
					// if bin index is within [0, m_nBin) interval 
					if (iBinW >= 0 && iBinW < m_nBin)				
						rHtm[iBinW] += 1.0f;
				}

				if (bR)
				{
					iBinR = (wPtr[iT].x - intervalR.x) * inv_r * m_nBin;
					// if bin index is within [0, m_nBin) interval 
					if (iBinR >= 0 && iBinR < m_nBin)				
						wHtm[iBinR] += 1.0f;
				}
			}
		}
	}

	void     Pyramid(uint8 exeFlags,
				        	 uint8 bufFlags)
	{
		if (exeFlags == EXEC_H)
		{
			bool bR = bufFlags & BUFFER_R;
			bool bW = bufFlags & BUFFER_W;

			C * WHtm = histogram.hPtrW();
			C * RHtm = histogram.hPtrR();

			C * WPmd = pyramid.hPtrW();
			C * RPmd = pyramid.hPtrR();

			for (uint32 iBin = 0; iBin < m_nBin; iBin++)
			{
				if (bW) WPmd[iBin] = WHtm[iBin];
				if (bR) RPmd[iBin] = RHtm[iBin];
			}

			uint32 iPmd = m_nBin;
			uint32 nPmd = 0;

			// while number of elements on a pyramid level is greater than one
			while (iPmd > 1)
			{
				// upper level has 2 times less bins cmpd to lower level
				uint32 nBin = iPmd >> 1;

				// for each element on the current pyramid level
				for (uint32 iBin = 0; iBin < nBin; iBin++)
				{	
					// each element is a sum of 2 elements below
					if (bW) WPmd[nPmd+iBin+iPmd] = WPmd[nPmd+iBin*2+0] + WPmd[nPmd+iBin*2+1];
					if (bR) RPmd[nPmd+iBin+iPmd] = RPmd[nPmd+iBin*2+0] + RPmd[nPmd+iBin*2+1];
				}

				// adding offsets means going to the next pyramid level
				nPmd += iPmd;

				// decrease number of elements by two
				iPmd = iPmd >> 1;			
			}
		}
	}

	void     Scan(uint8 exeFlags, 
		            uint8 bufFlags)
	{
		if (exeFlags == EXEC_H)
		{
			bool bR = bufFlags & BUFFER_R;
			bool bW = bufFlags & BUFFER_W;

			C * WHtm = histogram.hPtrW();
			C * RHtm = histogram.hPtrR();

			C * WScn = scan.hPtrW();
			C * RScn = scan.hPtrR();

			C v;

			memset(&v, 0, sizeof(v));

			if (bR) RScn[0] = v;
			if (bW) WScn[0] = v;

			for (uint iBin = 1; iBin <= m_nBin; iBin++)
			{
				if (bR) RScn[iBin] = RScn[iBin-1] + RHtm[iBin-1];
				if (bW) WScn[iBin] = WScn[iBin-1] + WHtm[iBin-1];
			}
		}
	}

	void     PrefixScan(uint8 exeFlags, 
		                  uint8 bufFlags)
	{
		if (exeFlags == EXEC_H)
		{
			bool bR = bufFlags & BUFFER_R;
			bool bW = bufFlags & BUFFER_W;

			C * WHtm = histogram.hPtrW();
			C * RHtm = histogram.hPtrR();

			C * WScn = scan.hPtrW();
			C * RScn = scan.hPtrR();

			if (bR) RScn[0] = RHtm[0];
			if (bW) WScn[0] = WHtm[0];

			for (uint iBin = 1; iBin < m_nBin; iBin++)
			{
				if (bR) RScn[iBin] = RScn[iBin-1] + RHtm[iBin];
				if (bW) WScn[iBin] = WScn[iBin-1] + WHtm[iBin];
			}

			if (bR) RScn[m_nBin] = RScn[m_nBin-1];
			if (bW) WScn[m_nBin] = WScn[m_nBin-1];
		}
	}
};

typedef THistoPyramid<float >			f_HistoPyramid;
typedef THistoPyramid<float2>			f2HistoPyramid;

#endif